package com.cet.algorithm.回溯.组合总和3;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @program: cet-practice
 * @description: 组合总和3
 * @author: 陈恩涛
 * @create: 2023-05-27 22:06
 **/
public class LC216 {

    // 结果集
    List<List<Integer>> result = new LinkedList<>();

    // 存放遍历的临时组合
    LinkedList<Integer> path = new LinkedList<>();

    /**
     * 求1-9之间找出所有相加之和为 n 的 k 个数的组合
     * @param k 组合元素的个数
     * @param n 和
     * @return 组合的集合
     */
    public List<List<Integer>> combinationSum3(int k, int n) {
        combineHelper(k, n, 1);
        return result;
    }

    public void combineHelper(int k, int n, int startIndex) {

        // 剪枝
        if (n < 0) {
            return;
        }

        // 递归终止
        if (path.size() == k) {
            if (n == 0) {
                result.add(new ArrayList<>(path));
            }
            return;
        }

        //单层逻辑
        for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
            path.add(i);
            combineHelper(k, n - i, i + 1);
            path.removeLast();
        }
    }

    public static void main(String[] args) {
        LC216 lc216 = new LC216();
        System.out.println(lc216.combinationSum3(3, 9));
    }
}
